COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input rwflet
C00006 ENDMK
C⊗;
\input rwflet
\rwflet
\address
TO WHOM IT MAY CONCERN
\body

Alan Hu collaborated with me in the Spring of 1988, on a piece of research
in the analysis of algorithms.  It was not toy research; I had a question
I had intended to investigate myself, and I expected it to be moderately
difficult.  Specifically, I wanted to investigate whether search of a
dictionary or other ordered table with associated probabilities can be done
with reasonable efficiency by the heuristic of always making the
probe that yields maximum information.  If there were a small numerical 
bound on the difference in expected running time between the heuristic algorithm
and an optimized algorithm, there would be a case for using the more easily
constructed heuristic method.

Alan began by conducting well-instrumented empirical studies.  Because we could
examine the performance of the algorithms on many subproblems, we were able
to see qualitatively the situations in which the heuristic algorithm was weak.
Eventually we found a class of problems on which the average difference
between the optimal and the heuristic algorithm could be made arbitrarily
large.  We then worked on simplifying the originally messy
characterization of such counterexamples.  We are continuing that investigation
now (Fall 1988).  Alan is a full participant in what I consider work of
substantial value.  Generally, I have sketched a plan of attack broadly, but
he has made interesting and unexpected discoveries within this framework.

There is no question in my mind about his suitability for any Ph.D. program.
He has already shown several times the ability to do publishable research.
His grades and his formidable list of honors and awards speak for themselves.
Even at grade-inflated Stanford, a 4.05 grade point average is very strong.
I would breathe a note of criticism if I could, just to preserve plausibility, 
but I really can't think of any.
\closing

Robert W. Floyd
\end